package com.github.ybqdren.chapter1.dynamicprogramming.p509;

/**
 * @author Wen(Joan) Zhao
 * @time 2022/1/8 14:05
 * @package com.github.ybqdren.chapter1.dynamicprogramming
 * @description  509. 斐波那契数  https://leetcode-cn.com/problems/fibonacci-number/
 **/
public class p509 {
    public static void main(String[] args) {
//        p509 instance = new p509();
//        instance.fib_1(2);
/*          fib_1(2);
          fib_2(2);
          fib_3(2);*/
    }

    // 针对方法三的状态优化
    /**
        一个细节优化：
            根据斐波那契数列的状态来转移方程，当前状态之和之前的两个状态有关，其实并不需要那么长的一个 DP Table 来存储所有的状态
            只要想办法存储之前的两个状态就行了。所以可以进行进一步的优化，把空间复杂度降为 O(1)

        状态压缩：
            这个技巧就是 状态压缩
            - 每次状态转移只需要 DP Table 中的一部分，那么可以尝试使用状态压缩来缩小 DP Table 的大小，只记录必要的数据，下面这个例子就
                相当于把 DP Table 的大小从 N 缩小到 2.
            - 在本书后面的动态规划例子中，一般是把一个二维的 DP Table 压缩成一堆，即把空间复杂度从 O(N^2) 压缩到 O(N)

        为什么没有涉及到 最优子结构 ？
            - 因为斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在说明重叠子问题的消除方法，演示为得到最优解法而逐步求精的过程
     */
    public static int fib_4(int n) {
        if(n == 0){ return 0; }
        if(n == 1 || n == 2){ return 1; }
        int prev = 1,curr = 1;
        for(int i = 3;i <= n;i++){
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }


    // 方法三：dp（动态规划） 数组的迭代解法
    /**
        受方法二 “备忘录” 的启发，我们可以把这个 “备忘录” 独立成一张表（看作 DP Table），然后在这张表上完成 “自底向上” 的推算。

        状态转移方程：描述问题结构的数学形式
                    | 1 , n = 12
            f(n) =
                    | f(n-1) + f(n-2) ,n > 2

            为什么叫状态转移？
                - 把 f(n) 想作一个状态 n，这个状态 n 是由状态 n-1 和状态 n-2 相加转移而来。

            状态转移方程直接代表着暴力解法：
                - 方法一二三 ，三种解法中所有的操作，都是围绕着这个方程式的不同表现形式，所以，状态转移方程是解决问题的核心
                - 千万不要看不起暴力解法，动态规划问题最困难的就是写出这个暴力解法，即状态转移方程。只要写出暴力解法，优化方法无非是用 “备忘录” ，
                    还是 DP Table
     */
    public static int fib_3(int n) {
        if(n == 0){ return 0; }
        if(n == 1 || n == 2){ return 1; }
        int dp[] = new int[n + 1];

        // base case
        dp[1] = dp[2] = 1;
        for(int i = 3;i <= n;i++){
            dp[i] = dp[i - 1] + dp[i -2];
        }
        return dp[n];
    }


    // 方法二：带备忘录的递归解法
    /**
        使用备忘录解决暴力递归产生的重复子问题后，递归树变成了递归图：
            f(20) -> f(19) -> f(18) -> f(17) -> ... -> f(2) -> f(1)

            -备忘录：
                > 每次计算某个子问题的答案后别急着返回，先将其记到 “备忘录” 里
                    再返回，每次遇到一个子问题先去 “备忘录” 里查找，如果没找到再进行递归
                    找到了，直接用
                > 一般用数组来充当 “备忘录”，也可以使用哈希表（字典），思路都是一样的


        递归算法的时间复杂度 = 子问题个数 * 解决一个子问题需要解决的时间

            - 子问题个数：
                > 即图中节点的总数，由于本算法不允许冗余计算，
                  子问题就是 f(1) 、f(2) 、f(3) ... f(20)，数量和输入规模 N=20 成正比，所以子问题的个数为 O(N)
            - 解决一个子问题的时间：
                > 没有循环，只有 f(n-1) + f(n-2) 加法操作，时间复杂度为 O(1)

            所以本算法的时间复杂度是 O(N) ，比起下面的暴力递归，已经是优化很多了

        至此，带 “备忘录” 的递归解法的效率已经和迭代的动态规划解法是一样的了。
        实际上，这种解法和迭代的动态规划已经差不多了，只不过这种解法是一种 “自顶向下” 的，
        动态规划是 “自底向上” 的。
            - 自顶向下
                > 从规模较大的原问题，向下逐渐分解规模，直到分解到了 base case，然后
                    逐层返回答案。
            - 自底向上
                > 从最下面、最简单、问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到
                    我们想要的答案 f(20)，这就是动态规划的思路，也是为什么动态规划
                    一般都脱离了递归，而是由循环迭代完成计算的关键所在。
     */
    public static int fib_2(int n) {
        if(n == 0){ return 0; }
        // 使用数组作为 “备忘录” ，存储遇到的子问题
        int memo[] = new int[n + 1];
        return helper(memo,n);
    }

    static int helper(int[] arr , int n){
        // base case
        if(n == 1 || n == 2){ return 1; }
        // 在备忘录中查找子问题，如果找到就直接返回
        if(arr[n] != 0){ return arr[n]; }
        // 没有找到子问题，继续递归查找
        arr[n] = helper(arr,n - 1) + helper(arr,n - 2);
        return arr[n];
    }





    // 方法一：暴力递归

    /**
        递归树：
                         f(20)
              f(19)                f(18)
         f(18)    f(17)        f(17)    f(16)
        .......    .....          ..........
      f(1)  f(2)  f(1) f(2)

     从上面可以看出，想要计算原问题 f(20) ，就应该先计算出子问题 f(19) 和 f(18)
     要计算 f(19)，就要先计算出子问题 f(18) 和 f(17) , 以此类推
     最后当遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树也不再向下生长了。

     观察上面这个递归树，可以很明显地发现算法低效的原因：存在大量重复计算，比如 f(18)
     被计算了两次，而且以 f(18) 为根的这个递归树体量巨大，多算一遍会耗费大量的时间
     更何况还不止 f(18) 这一个节点会被重复计算，所以这个算法非常的低效。
     < 这就是动态规划问题的第一个性质：重叠子问题。 >


     -递归算法的复杂度计算？
        复杂度 = 子问题个数 * 解决一个子问题需要的时间

        >  子问题个数：
            即递归树中节点的总数。显然二叉树节点总数为指数级别的，所以求子问题个数的时间复杂度为 O(2^n)。

        > 解决一个子问题的时间：
            在本算法中，没有循环，只有 f(n-1) + f(n-2) 加法操作，所以时间复杂度为 O（1）

        所以此递归算法的复杂度为： O(2^n)，指数级别
     */
    public static  int fib_1(int n) {
        if(n == 0){ return 0; }
        if(n == 1 || n == 2){ return 1; }
        return fib_1(n - 1) + fib_1(n - 2);
    }

}
